package datastrucure.tree;

/**
 * @Author Fizz Pu
 * @Date 2021/4/16 下午8:25
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

/**
 * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 * 示例:
 * 给定如下二叉树，以及目标和 target = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 * 返回:
 *
 * [
 *    [5,4,11,2],
 *    [5,8,4,5]
 * ]
 */

/**
 *这很明显是一个dfs外加回溯的问题
 * 我现在最大的缺点就是整理思路的过程, 完全是混乱的
 * 5; 不是叶子节点; sum = 5; 节点 :5
 * 4 不是叶子节点 sum = sum + 4 = 9  节点5 , 4
 * 11 不是 sum = 20 节点5 4 11
 * 7 sum = 27 大于target 直接减枝 不再往下搜索
 * 回溯 sum = 20 路径5 4 11
 * 5 4 11 2 等于 是叶子节点 加入结果 然后回溯
 * 5 4
 * 5 8
 */


/**
 * 算法框架
 * sum: 求和, result: 返回值[[]] , tmp: 临时回溯的结果[]
 * dfs(root){
 *     if(root == null){return;}
 *
 *     sum += root.val;
 *     tmp.add(root);
 *
 *     if(sum == target && root.left == null && root.right == null){
 *         result.add(tmp)
 *     }
 *
 *
 *     dfs(root.left);
 *     dfs(root.right);
 *
 *     tmp中最后一个元素删除了
 *     sum -= root.val
 * }
 */


/**
 * 不知道何时回溯, 以为是左子树遍历结束后回溯
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LeeOffer34 {

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        traceBack(root, target, result, new ArrayList<>(), 0);
        return result;
    }

    private void traceBack(TreeNode root, int target, List<List<Integer>> res, List<Integer> tmp, int sum){
        if(root == null){
            return;
        }

        sum += root.val;
        tmp.add(root.val);

        /* 存在负数, 无法减枝
        if(sum > target){
            return;
        }
        */

        if(sum == target && root.right == null && root.left == null){
            res.add(new ArrayList<>(tmp));
        }

        traceBack(root.left, target, res, tmp, sum);
        traceBack(root.right, target, res, tmp, sum);

        tmp.remove(tmp.size() - 1);
        sum -= root.val;
    }
}
